1000
862 417 848 334 434 61 919 162 893 972 179 144 502 83 750 457 908 150 264 45 564 771 312 84 559 492 22 123 551 486 97 38 609 318 213 582 978 26 433 760 520 980 835 462 763 56 627 672 573 370 321 741 986 77 178 128 638 458 19 603 682 281 51 29 185 311 258 543 373 552 600 579 887 498 983 812 664 255 853 341 996 681 730 110 376 537 820 544 945 188 536 122 604 970 884 850 946 840 953 279 711 880 256 326 249 606 105 193 429 578 891 5 632 999 446 788 818 94 759 60 398 153 242 969 503 53 518 290 186 138 411 240 666 158 215 166 285 991 663 787 981 630 17 560 628 451 639 263 675 843 841 76 852 54 134 926 657 191 576 808 233 590 842 194 777 333 567 470 934 6 222 933 633 554 421 792 516 487 959 856 703 465 419 146 677 776 844 674 270 229 418 456 988 687 673 561 587 70 592 142 671 208 795 354 474 416 496 790 327 247 265 78 15 965 967 11 151 384 380 976 436 324 625 588 351 868 829 968 546 88 37 645 819 93 899 350 526 274 485 268 881 183 47 68 238 676 528 269 557 857 907 405 785 214 118 406 888 33 439 960 72 706 540 538 660 30 169 916 975 683 921 620 895 35 562 164 997 513 444 608 447 102 299 221 173 181 119 424 929 218 547 44 402 723 307 148 640 344 226 408 511 187 556 534 74 4 817 356 549 565 571 171 495 200 635 652 355 67 865 353 126 254 599 43 489 85 273 152 202 338 523 9 758 18 752 782 719 956 992 728 846 504 514 497 225 718 71 973 116 141 364 767 831 722 385 927 708 984 394 239 971 332 198 396 735 248 357 762 935 409 643 8 41 729 452 646 387 550 811 168 594 869 699 65 707 476 943 298 66 57 363 278 994 262 232 623 135 938 925 25 713 704 482 46 749 244 939 796 480 117 243 210 688 283 491 305 533 100 207 870 120 21 277 175 253 651 445 24 950 595 656 149 797 584 427 698 954 20 275 955 747 696 766 764 163 481 962 924 689 806 772 602 867 230 801 106 621 659 415 922 346 246 276 966 50 667 228 42 501 596 379 555 568 107 615 27 136 377 101 203 822 957 715 553 517 314 488 684 323 601 815 212 901 932 650 478 670 32 889 393 530 931 581 490 649 288 308 197 349 304 345 328 845 129 252 724 644 598 605 317 805 648 825 133 710 535 653 580 325 223 721 622 789 358 167 403 839 172 432 464 725 784 108 280 743 397 828 593 569 423 823 690 271 878 211 732 941 287 985 654 589 742 453 261 294 858 336 814 702 259 679 851 738 422 995 519 160 532 506 337 139 541 438 89 539 847 36 531 82 669 998 468 295 662 879 320 804 803 769 220 855 441 791 773 39 196 802 734 712 448 348 824 125 383 914 515 113 665 300 360 894 902 99 362 655 114 940 289 201 339 691 309 641 982 322 821 392 182 389 331 236 619 86 548 170 365 159 783 7 923 731 127 103 209 695 890 343 479 286 95 369 301 574 155 905 195 739 121 475 779 745 1000 833 216 399 958 977 407 371 461 428 964 716 124 284 473 156 386 335 898 73 140 368 292 678 484 859 794 913 912 410 374 75 510 700 205 800 875 112 507 765 993 809 472 834 16 296 466 942 388 830 827 199 237 930 529 637 81 267 147 854 206 737 570 575 477 91 634 319 467 610 770 757 780 381 241 566 401 694 111 775 542 342 726 733 431 12 413 961 204 697 90 329 642 426 367 442 522 414 499 906 611 951 658 521 282 272 250 104 692 224 109 974 161 781 949 412 143 717 727 98 352 505 347 96 636 306 293 257 629 863 904 793 165 420 917 400 832 849 989 69 631 987 40 13 586 435 838 450 910 740 471 563 63 524 761 192 483 235 359 189 378 227 909 508 1 774 176 3 500 145 572 768 297 618 756 937 577 799 816 437 231 302 810 647 545 266 493 874 313 260 882 59 28 115 340 990 361 58 184 390 459 157 661 48 705 837 963 897 612 911 826 613 245 404 720 685 469 614 798 876 860 64 936 443 813 154 494 680 872 778 23 807 219 892 372 751 52 736 375 440 463 871 80 395 668 597 616 34 896 886 87 137 583 748 624 558 31 512 291 746 686 382 877 947 920 132 786 525 903 755 2 449 62 455 979 425 864 92 527 454 873 585 315 234 190 217 948 79 626 251 49 303 754 753 915 10 310 944 430 861 836 130 180 883 55 366 709 952 744 918 131 460 607 177 900 928 391 701 617 14 885 693 509 174 330 714 866 591 316 
875 555 276 284 458 225 643 369 333 440 391 723 884 668 846 634 359 87 401 809 715 235 119 654 672 157 78 616 648 856 651 878 273 182 330 11 387 554 591 622 962 534 580 18 150 824 578 135 575 698 579 468 414 45 641 269 207 32 858 630 883 437 792 376 782 23 565 27 739 346 199 22 629 222 76 423 952 179 481 980 332 428 208 542 716 819 209 610 539 63 511 748 890 733 43 586 926 968 146 463 601 40 343 349 512 897 257 764 874 184 837 382 995 134 370 464 626 175 732 445 942 194 772 752 189 650 388 833 921 312 623 59 913 24 492 712 775 128 929 533 53 508 365 364 673 598 577 389 605 123 176 425 912 584 232 2 703 553 801 187 563 137 569 816 473 794 86 66 976 904 305 412 272 302 761 99 185 173 155 434 958 133 234 867 393 750 531 644 908 334 721 212 315 868 725 159 329 224 562 693 371 275 363 836 637 558 719 793 589 474 203 144 395 490 581 426 892 174 743 854 438 15 239 210 844 104 954 108 435 728 663 932 90 31 612 436 455 948 177 204 759 692 255 183 677 471 287 549 572 169 501 861 493 488 755 245 765 75 905 781 751 165 444 594 3 620 111 849 653 448 931 503 609 778 823 660 736 834 881 394 935 140 228 124 532 688 647 41 632 608 158 592 311 362 825 956 791 320 139 68 285 344 483 316 383 314 760 141 919 162 166 516 701 535 197 386 339 848 317 509 944 160 974 244 500 396 178 263 136 353 551 504 270 615 479 138 324 48 267 850 168 607 682 186 295 206 442 424 406 88 997 308 46 29 784 661 785 28 441 839 505 116 702 635 953 466 567 188 20 163 142 400 862 480 101 418 726 544 380 392 277 452 939 288 810 55 831 604 79 34 927 624 681 690 621 251 864 524 783 754 959 37 404 181 170 254 779 118 832 96 103 109 125 180 583 576 246 889 679 538 407 258 8 410 909 740 297 190 361 636 13 381 805 69 860 201 975 461 741 525 89 631 93 808 638 894 768 390 886 415 313 453 459 642 510 171 281 711 470 568 731 417 529 130 476 573 937 243 773 356 936 658 347 97 477 666 788 820 102 928 261 427 686 827 656 990 39 938 945 306 815 560 409 338 689 796 795 800 978 219 902 552 355 443 934 348 918 756 350 485 322 491 857 674 734 402 790 33 595 957 447 499 777 218 304 342 593 216 422 526 280 200 683 680 806 67 502 618 494 770 924 233 352 151 627 366 58 253 649 985 991 420 744 722 5 368 498 153 52 215 845 853 351 372 685 696 943 880 161 299 882 221 933 303 429 152 720 522 419 992 110 786 988 71 520 126 335 986 724 973 114 236 999 888 851 213 515 230 92 328 73 373 842 293 969 379 145 489 993 44 132 36 967 300 156 737 309 9 877 652 855 454 229 753 994 198 265 486 310 10 530 714 664 4 416 262 811 143 840 478 559 984 684 375 735 557 747 457 54 57 961 291 264 62 901 706 556 195 298 286 367 757 487 742 749 247 107 787 91 659 398 885 774 403 327 496 699 112 700 814 893 460 687 331 979 513 691 625 941 231 671 336 129 738 268 340 669 838 193 131 879 279 847 70 960 202 289 172 657 61 713 450 548 717 903 639 899 676 154 127 675 82 617 430 911 729 730 1 545 100 326 360 917 7 413 645 628 602 319 12 50 122 6 891 585 727 914 307 758 587 30 378 517 240 259 946 826 519 606 695 475 966 582 704 965 708 47 98 421 507 294 266 640 514 65 377 242 910 301 547 895 117 949 982 989 972 528 766 561 646 321 710 26 611 405 432 248 841 983 80 963 876 670 105 354 707 465 227 325 597 397 278 633 780 776 662 947 214 205 828 341 550 896 865 600 763 596 223 399 541 121 323 56 35 866 678 771 449 113 543 923 16 95 859 818 148 431 164 77 115 869 167 971 746 951 812 60 357 887 852 981 745 571 220 802 374 484 798 955 523 249 241 871 411 769 283 940 252 537 922 495 799 566 762 472 705 467 446 84 667 85 916 603 106 94 385 292 822 998 613 21 238 296 872 898 1000 835 536 439 64 250 821 345 804 925 920 964 915 192 694 482 226 462 74 456 217 518 83 655 72 718 49 337 843 256 564 807 870 433 599 977 196 863 900 789 970 38 614 817 907 829 274 497 574 384 191 19 469 271 290 408 318 906 709 17 987 619 930 506 25 546 260 830 237 540 665 570 147 813 358 14 697 950 81 590 803 521 527 120 588 996 282 211 42 873 767 797 451 51 149